package com.gitee.ywj1352.leecode;

/**
 * @author wenjie.yang on 2019/6/27.
 */
public class Demo {


    public static void main(String[] args) {
        Demo demo = new Demo();
        int[][] arr = {{1,2,3},{2,3,4},{4,9,10}};
        System.out.println(demo.searchMatrix(arr,9));
    }

    /**
     * [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0||matrix[0].length == 0 ||matrix[0][0]>target  || matrix[matrix.length-1][matrix[0].length-1]<target){
            return false;
        }
        // 升序
        for(int i= 0;i<matrix.length ;i++){
            if(matrix[i][0]>target  || matrix[i][matrix[i].length-1]<target) continue;
            //二分查找
            int[] arr= matrix[i];
            if (halfSearch(arr,target)){
                return true;
            }else {
                continue;
            }
        }
        return false;
    }


    public boolean halfSearch(int[] arr ,int  target){
        int low = 0,heigh  = arr.length;
        while(heigh>=low){
            int med = (heigh +low)/2;
            if (target == arr[med]){
                return true;
            }else if(target>arr[med]){
                low = med +1;
            }else if(target<arr[med]){
                heigh = med-1;
            }
        }
        return false;
    }


    /**
     * 输入:
     * nums1 = [1,2,3,0,0,0], m = 3
     * nums2 = [2,5,6],       n = 3
     *
     * 输出: [1,2,2,3,5,6]
     */
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int [] arr = new int [m+n];
        return null;
    }


}
